#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 210;
const int M = 1010;
const int inf = 0x3f3f3f3f;

int n, m;

namespace F { // max_flow
	const int M = 1e4 + 10;
    int h[N], now[N], d[N], cnt = 1, S, T;
    struct edge { int v, w, nxt; } e[M << 1];
    inline void tlink(int x, int y, int w) { e[++cnt] = (edge) { y, w, h[x] }; h[x] = cnt; }
    inline void link(int x, int y, int w) { tlink(x, y, w); tlink(y, x, 0); }
    inline void setst(int s, int t) { S = s; T = t; }
    queue < int > q;
	void reset() { cnt = 1; rep(i, 1, n) h[i] = 0; }
    bool bfs() {
		while(q.size()) q.pop(); q.push(S); memset(d, 0, sizeof d); d[S] = 1; now[S] = h[S];
		while(!q.empty()) {
			int x = q.front(); q.pop();
			for(int i = h[x], y; i; i = e[i].nxt)
				if(e[i].w && !d[y = e[i].v]) {
					d[y] = d[x] + 1; q.push(y); now[y] = h[y];
					if(y == T) return 1;
				}
		} return 0;
    }
    int dinic(int x, int flow) {
		if(x == T) return flow;
		int res = flow;
		for(int i = now[x], y; i && res; i = e[i].nxt) {
			now[x] = i;
			if(e[i].w && d[y = e[i].v] == d[x] + 1) {
				int k = dinic(y, min(res, e[i].w));
				if(!k) d[y] = 0; e[i].w -= k; e[i ^ 1].w += k; res -= k;
			}
		}
		return flow - res;
    }
    ll runit() {
		ll maxflow = 0,flow;
		while(bfs()) while(flow = dinic(S, inf)) maxflow += flow;
		return maxflow;
    }
}

struct edge { int v, w, nxt; } e[M << 1];
int h[N];
int u[M], v[M], w[M], cnt = 1;
int p[N], q[N], top;
bool ban[N << 1];

void link(int x, int y, int w) { e[++cnt] = (edge) { y, w, h[x] }; h[x] = cnt; }

int get(int x, int y) {
	F :: reset(); rep(i, 1, m) F :: link(u[i], v[i], w[i]), F :: link(v[i], u[i], w[i]);
	F :: setst(x, y); return F :: runit();
}

void build(int l, int r) {
	if(l == r) return; int x = p[l], y = p[r], w = get(x, y);
	link(x, y, w); link(y, x, w);
	top = 0; int cur = l;
	rep(i, l, r) {
		if(!F :: d[p[i]]) q[++top] = p[i];
		else p[cur++] = p[i];
	} int lcur = cur;
	rep(i, 1, top) p[cur++] = q[i];
	build(l, lcur - 1); build(lcur, r);
}

int pos;

void dfs(int x, int p) {
	for(int i = h[x], y = e[i].v; i; i = e[i].nxt, y = e[i].v) {
		if(!ban[i] && y ^ p) {
			dfs(y, x); if(pos == 0 || e[i].w < e[pos].w) pos = i;
		}
	}
}

int ans;
vec pot;

void divide(int x) {
	pos = 0; dfs(x, 0); if(pos == 0) return pot.eb(x), void();
	ban[pos] = ban[pos ^ 1] = true; ans += e[pos].w;
	x = e[pos ^ 1].v; int y = e[pos].v;
	divide(x); divide(y);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in, m = in;
	rep(i, 1, m) u[i] = in, v[i] = in, w[i] = in;
	rep(i, 1, n) p[i] = i;
	build(1, n); divide(1); printf("%d\n", ans); for(auto v : pot) printf("%d ", v);
	puts("");
	return 0;
}
